Sets, Relations, and Functions
Core definitions and proof moves for set operations, equivalence relations, and function types at Math 55 rigor.
Keyboard Shortcuts
💡 Pro tip: Use keyboard shortcuts for faster studying!
Study Smart Tips for Sets, Relations, and Functions
Master these concepts using proven study techniques that actually work:
Active Recall
Test yourself before flipping each card to strengthen memory retention
Spaced Repetition
Review difficult cards more frequently than easy ones
Multiple Sessions
Break study time into shorter, focused sessions
Explain Aloud
Verbalize answers to reinforce understanding
Questions Covered in This Set
10 cards to master
What is the official proof strategy for showing A = B?
Prove both inclusions: A ⊆ B and B ⊆ A. Each inclusion starts 'Let x ∈ A be arbitrary' and ends '...hence x ∈ B' (axiom of extensionality).
Unpack 'A ⊆ B' as a logical statement.
∀x (x ∈ A ⇒ x ∈ B).
Define the power set and give its size for a finite A.
𝒫(A) = {S : S ⊆ A}, the set of all subsets. |𝒫(A)| = 2^|A|.
What is a relation from A to B, officially?
Any subset R ⊆ A × B. No 'rule' required — just a set of ordered pairs; aRb means (a,b) ∈ R.
State the three properties defining an equivalence relation.
Reflexive (∀a, aRa), symmetric (aRb ⇒ bRa), and transitive (aRb ∧ bRc ⇒ aRc).
What does the partition theorem say about equivalence classes?
The classes [a] = {x : x ∼ a} are nonempty, cover A, and any two are identical or disjoint. Conversely, every partition induces an equivalence relation.
Why are [a] and [b] equal whenever they share an element c?
c ∈ [a] ∩ [b] gives a ∼ c and c ∼ b, so a ∼ b by symmetry + transitivity; then x ∼ a ⇔ x ∼ b, hence [a] = [b].
What is the quotient A/∼?
The set of all equivalence classes of A under ∼ — e.g. ℤ/nℤ from congruence mod n.
State the De Morgan identity proved in the lecture.
A \ (B ∩ C) = (A \ B) ∪ (A \ C) — set identities are logical identities in costume.
Give the quartic-flavored example of an equivalence relation.
On monic quartics over ℂ: p ∼ q iff q(x) = p(x + c) for some c. Reflexive via c = 0, symmetric via −c, transitive via c₁ + c₂ — the depressed-quartic shift.
